package BinaryTree;

//二叉树的序列化和反序列化: https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/
//时间复杂度: O(n)
public class Codec {
	
	
	// Encodes a tree to a single string.
	//-------------------------序列化----------------------------
	public void dfs(TreeNode root,StringBuilder builder) {
		//dfs功能: 将树root进行序列化， 遍历顺序: 先序遍历(中左右)
		if(root==null) {
			builder.append("#,");
		}
		else {
			builder.append(root.val+",");   //当前位置序列化
			dfs(root.left,builder);         //将左孩子序列化
			dfs(root.right,builder);        //将右孩子序列化
			//我相信其能帮我处理左右孩子的序列化，因此只要将当前层序列化
		}	
	}
    public String serialize(TreeNode root) {
    	StringBuilder builder=new StringBuilder();
        dfs(root,builder);
    	return builder.toString();
        
    }
    

    // Decodes your encoded data to tree.
    //-------------------------反序列化----------------------------
    //全局遍历cnt表示当前正处理的节点
    public static int cnt;
    public TreeNode g(String[] vals) {
    	String val=vals[cnt++];  //拿到第cnt个节点的val
    	if(val.equals("#")) {    //为#表示空节点
    		return null;
    	}
    	else {
    		TreeNode root=new TreeNode(Integer.parseInt(val));  //构造当前节点
    		//我相信dfs能帮我完成树的构建，因此现在我有了构建后的左右子树
    		//因此，我只需要连接左右孩子就可以了;
    		root.left=g(vals);
    		root.right=g(vals);
    		return root;
    	}
    }
    public TreeNode deserialize(String data) {
        String[] vals=data.split(",");
        cnt=0;        //cnt为静态成员，因此必须先置空，否则为脏数据
        return g(vals);
    }
}
